package com.devshephard.rpcframework.acm.tree.util;

import java.util.*;
import java.util.stream.Collectors;

public class LCR_085 {

    public static void main(String[] args) {

        int n = 5;

        List<String> resultList = new ArrayList<>();
        List<String> lastResList = new ArrayList<>();

        for (int i = 0; i < n * 2; i++) {

            if(i == 0){
                resultList.add("(");
                continue;
            }

            int startPointer = (int)Math.pow(2,(i - 1)) - 1;

            for (int j = 0; j < (int)Math.pow(2,i - 1) ; j++) {


                final String s = resultList.get(startPointer);
                final String t1 = new String(s + ")");
                final String t2 = new String(s + "(");
                resultList.add(t1);
                resultList.add(t2);

                startPointer ++;

            }
        }

        for (String s : resultList) {
            //校验是否合法
            if (s.length() == n * 2){
                final String validStr = new String(s);
                List<String> vaild = Arrays.stream(validStr.split("")).collect(Collectors.toList());
                for (int k = 0; k < vaild.size(); k++) {
                    if ("(".equals(vaild.get(k))){
                        for (int l = k + 1; l < vaild.size(); l++) {
                            if(")".equals(vaild.get(l))){
                                vaild.set(l,null);
                                break;
                            }
                        }
                    }
                }
                final long count1 = vaild.stream().filter(v -> v != null).count();
                final long count2 = vaild.stream().filter(v -> v == null).count();
                if ( count1 == count2){
                    System.out.println(s);
                    lastResList.add(s);
                }
            }
        }


        }
    }


